/**
 * https://leetcode.cn/submissions/detail/565152013/
 * 1539. 第 k 个缺失的正整数
 * easy, 黄伟杰 2024.9.16
 * 二分查找
 */

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int findKthPositive(vector<int> &arr, int k)
    {
        if (k < arr[0])
            return k;
        int l = 0, r = arr.size();
        while (l < r)
        {
            int mid = l + r >> 1;
            int x;
            if (mid < arr.size())
                x = arr[mid];
            else
                x = INT_MAX;
            if (x - mid - 1 >= k)
            {
                r = mid;
            }
            else
                l = mid + 1;
        }
        return k + l;
    }
};